package com.sicheng.蓝桥.练习题.dp.状态压缩;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/6 23:08
 */
public class 最短Hamilton距离 {
    /**
     * 给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。
     * Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
     * 输入格式
     * 第一行输入整数 n。
     * 接下来 n 行每行 n 个整数，其中第 i 行第 j 个整数表示点 i 到 j 的距离（记为 a[i,j]）
     * 对于任意的 x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]
     * 输出格式
     * 输出一个整数，表示最短 Hamilton 路径的长度。
     * 数据范围
     * 1≤n≤20
     * 0≤a[i,j]≤10^7
     * 输入样例：
     * 5
     * 0 2 4 5 1
     * 2 0 6 5 3
     * 4 6 0 8 3
     * 5 5 8 0 5
     * 1 3 3 5 0
     * <p>
     * 输出样例：
     * 18
     */

    //dp[i][j]
    // 从0-i 走到i走过的所有点是j (j是2进制状态===111001 表示走过0,3,4,5号点)
    static long[][] dp = new long[21][1 << 20];
    // 转移过程可以有倒数第二个点转移而来,假设倒数第二个点是k
    // 0----k-i  dp[i][j]= min{dp[i][j],dp[k][j-{i}]+g[k][i]}
    // 从0到k  处的状态是  j状态扣除点i得到
    static int[][] g = new int[21][21];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = scanner.nextInt();
            }
        }

        for (long[] longs : dp) {
            Arrays.fill(longs, Long.MAX_VALUE >> 2);
        }
        // 从0号点开始 走过0号点。也就是从0号点开始
        dp[0][1] = 0;
        for (int j = 1; j < 1 << n; j++) {
            for (int i = 0; i < n; i++) {
                if (((j >> i) & 1) == 1) {
                    for (int k = 0; k < n; k++) {
                        if (((j >> k) & 1) == 1)
                            // 由j 状态扣除一个点也就是i 就是0-k的状态
                            dp[i][j] = Math.min(dp[i][j], dp[k][j - (1 << i)] + g[k][i]);
                    }

                }
            }
        }

        System.out.println(dp[n - 1][(1 << n) - 1]);


    }
}
